package kmp;

/**
 * @author zhengTao
 * @version 1.0
 * @description: 重复的子字符串
 * @date 2022/10/22 15:08
 */
public class Demo459 {
    public static void main(String[] args) {
        String s="abac";
        boolean b = repeatedSubstringPattern2(s);
        System.out.println(b);
    }
    //方法1
    public static boolean repeatedSubstringPattern(String s) {
        String newStr=s+s;
        String substring = newStr.substring(1, newStr.length() - 1);
        return substring.contains(s);
    }
    //方法二
    public static boolean repeatedSubstringPattern2(String s) {
        //kmp 求next数组
        int[] next=getNext(s);
        //next[next.length-1]==0; 肯定不是多个字串组成的;
        //===========================
        //next[next.length-1]最大公共字串长度
        //s.length()-next[next.length-1】 如果是重复字串组成，这个就是组成整个字符串的最小字串单位
        //如果能整除，则是重复字符，不能整除则不是重复子串
        if(next[next.length-1]!=0&&(s.length()%(s.length()-next[next.length-1])==0)){
            return true;
        }else {
            return false;
        }
    }

    private static int[] getNext(String s) {
        int[] next=new int[s.length()];
        next[0]=0;
        int j=0;
        char[] chars = s.toCharArray();
        for (int i = 1; i < chars.length; i++) {
           while (j>0&&chars[i]!=chars[j]){
               j=next[j-1];
           }
           if(chars[i]==chars[j]){
               next[i]=++j;
           }
        }
        return next;
    }
}
